package com.michael.demos.base.java.sort;

import java.util.Arrays;

/**
 * 类功能描述:
 * <pre>
 *   计数排序
 *   1. 花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max
 *   2. 开辟一块新的空间创建新的数组 B，长度为 ( max – min + 1)
 *   3. 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
 *   4. 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数
 * </pre>
 *
 * @author Michael
 * @version 1.0
 * @date 2020/9/24 9:35
 */
public class CountingSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) {

        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int[] maxAndMin = getMaxAndMin(arr);

        return countingSort(arr, maxAndMin);
    }

    private int[] countingSort(int[] arr, int[] maxAndMin) {

        int maxVal = maxAndMin[0];
        int minVal = maxAndMin[1];

        if (minVal < 0) {
            throw new RuntimeException("计数排序不支持负数排序");
        }

        int bucketLen = maxVal - minVal + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value - minVal]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j + minVal;
                bucket[j]--;
            }
        }
        return arr;
    }

    private int[] getMaxAndMin(int[] arr) {
        int maxValue = arr[0];
        int minValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
            if (minValue > value) {
                minValue = value;
            }
        }
        return new int[]{maxValue, minValue};
    }

}
